// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;

struct Solution {}

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
      Solution::build_tree(1, n+1)
    }
    pub fn build_tree(l: i32, r: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
      let mut ret = vec![];
      if l == r {
        return vec![None];
      }
      for i in l..r {
        for left in  Solution::build_tree(l, i).iter() {
          for right in Solution::build_tree(i+1, r).iter() {
            ret.push(Some(Rc::new(RefCell::new(TreeNode {
              val: i,
              left: left.clone(),
              right: right.clone()
            }))));
          }
        }
      }
      ret
    }
}